package com.sgg.algorithm.sort;


import java.util.Arrays;

/**
 * 插入排序的升级法
 */
public class ShellSort {
    public static void main(String[] args) {

    }


    //交换法 效率很低
    public static void sortExchange(int[] arr) {
        int count = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        int temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
//            System.out.println(count+"次:"+Arrays.toString(arr));
        }
    }

    //移动法 效率比较高,类似插入排序
    public static void sortMove(int[] arr) {
        //步长
        int move = 3;
        for (int gap = arr.length / move; gap > 0; gap /= move) {
            for (int i = gap; i < arr.length; i++) {
                int insertIndex = i;
                int insertValue = arr[i];
                if (arr[insertIndex] < arr[insertIndex - gap]) {
                    while (insertIndex - gap >= 0 && insertValue < arr[insertIndex - gap]) {
                        arr[insertIndex] = arr[insertIndex - gap];
                        insertIndex -= gap;
                    }
                    arr[insertIndex] = insertValue;
                }
            }
        }
    }

    public static void demo() {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        /**
         * 第一次 5组 每组2个
         * i=5 j=0
         * i=6 j=1
         * i=7 j=2
         * i=8 j=3
         * i=9 j=4
         */
        for (int i = 5; i < arr.length; i++) {
            for (int j = i - 5; j >= 0; j -= 5) {
                if (arr[j] > arr[j + 5]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 5];
                    arr[j + 5] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
        /**
         * 第二次 2组,每组5个
         * i=2 j=0
         * i=3 j=1
         * i=4 j=2,0
         * i=5 j=3,1
         * i=6 j=4,2,0
         * i=7 j=5,3,1
         * i=8 j=6,4,2,0
         * i=9 j=7,5,3,1
         */
        for (int i = 2; i < arr.length; i++) {
            for (int j = i - 2; j >= 0; j -= 2) {
                if (arr[j] > arr[j + 2]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 2];
                    arr[j + 2] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
        /**
         * 第三次1组,每组10个
         * 1 0
         * 2 1,0
         * 3 2,1,0
         * 4 3,2,1,0
         * 5 4-0
         * 6 5-0
         * 7 6-0
         * 8 7-0
         * 9 8-0
         */
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0; j -= 1) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
